//
// Created by q on 2020/12/6.
//

#include "lowestCommonAncestor.h"
class Solution {
 public:
  TreeNode* ans;
  bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return false;
    bool lson = dfs(root->left, p, q);
    bool rson = dfs(root->right, p, q);
    if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
      ans = root;
    }
    return lson || rson || (root->val == p->val || root->val == q->val);
  }
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    dfs(root, p, q);
    return ans;
  }
};

